package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * lixw
 * 2021/11/5
 **/
public class MaximalSquare221 {

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        //正方形最大边
        int max = 0;
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i] - '0';
            max = Math.max(max, dp[0][i]);
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] - '0';
            max = Math.max(max,  dp[i][0]);
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                //(i-1,j-1)为右下方节点得最大正方形边长
                int preEdge = dp[i - 1][j - 1];
                int edge = 0;
                for (int k = 0; k <= preEdge; k++) {
                    if (matrix[i - k][j] == '1' && matrix[i][j - k] == '1') {
                        edge++;
                    } else {
                        break;
                    }
                }
                dp[i][j] = edge;
                max = Math.max(max, edge);
            }
        }
        return max * max;
    }



    public static void main(String[] args) {
        MaximalSquare221 m = new MaximalSquare221();
        List<char[][]> cases = new ArrayList<>();
        cases.add(new char[][] {{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}});
        for (char[][] c : cases) {
            System.out.println(ArraysUtils.formatChars(c)+ "\t"+ m.maximalSquare(c));
        }

    }
}
